|
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (''r'',''g'')-graph is defined to be a graph in which each vertex has exactly ''r'' neighbors, and in which the shortest cycle has length exactly ''g''. It is known that an (''r'',''g'')-graph exists for any combination of ''r'' ≥ 2 and ''g'' ≥ 3. An (''r'',''g'')-cage is an (''r'',''g'')-graph with the fewest possible number of vertices, among all (''r'',''g'')-graphs. If a Moore graph exists with degree ''r'' and girth ''g'', it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth ''g'' must have at least : vertices, and any cage with even girth ''g'' must have at least : vertices. Any (''r'',''g'')-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage. There may exist multiple cages for a given combination of ''r'' and ''g''. For instance there are three nonisomorphic (3,10)-cages, each with 70 vertices : the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one (3,11)-cage : the Balaban 11-cage (with 112 vertices). == Known cages == A degree-one graph has no cycle, and a connected degree-two graph has girth equal to its number of vertices, so cages are only of interest for ''r'' ≥ 3. The (''r'',3)-cage is a complete graph ''K''''r''+1 on ''r''+1 vertices, and the (''r'',4)-cage is a complete bipartite graph ''K''''r'',''r'' on 2''r'' vertices. Other notable cages include the Moore graphs: * (3,5)-cage: the Petersen graph, 10 vertices * (3,6)-cage: the Heawood graph, 14 vertices * (3,8)-cage: the Tutte–Coxeter graph, 30 vertices * (3,10)-cage: the Balaban 10-cage, 70 vertices * (3,11)-cage: the Balaban 11-cage, 112 vertices * (4,5)-cage: the Robertson graph, 19 vertices * (7,5)-cage: The Hoffman–Singleton graph, 50 vertices. * When ''r'' − 1 is a prime power, the (''r'',6) cages are the incidence graphs of projective planes. * When ''r'' − 1 is a prime power, the (''r'',8) and (''r'',12) cages are generalized polygons. The numbers of vertices in the known (''r'',''g'') cages, for values of ''r'' > 2 and ''g'' > 2, other than projective planes and generalized polygons, are: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cage (graph theory)」の詳細全文を読む スポンサード リンク
|